'''
输入一个复杂链表
（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），
请对此链表进行深拷贝，并返回拷贝后的头结点。
（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
'''
# 递归
# random指向了原始链表中的节点
class Solution:
    # 返回 RandomListNode
    def Clone(self, head):
        # write code here
        if not head:
            return
        newNode = RandomListNode(head.label)
        newNode.random = head.random
        newNode.next = self.Clone(head.next)
        return newNode
# 哈希表
'''
复杂链表复制，简单的O(n), O(n)解法
这道题只要能找到random指针的映射关系即可，可以考虑使用字典保存这种映射关系。
把所有节点放在一个list里面，然后计算random的映射字典(位置->位置)，然后复制一个新的list，依次赋值next和random
'''
